package com.tgy.algorithm.base.other;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class _判断子二叉树是否是整个二叉树的子序列 {

    public static BiTreeNode generalBiTreeNode() {

        /**
         *              0
         *           1     2
         *       3     4  5   6
         *
         *
         */
        BiTreeNode root = new BiTreeNode(0);

        root.left = new BiTreeNode(1);
        root.right = new BiTreeNode(2);

        root.left.left = new BiTreeNode(3);
        root.left.right = new BiTreeNode(4);

        root.right.left = new BiTreeNode(5);
        root.right.right = new BiTreeNode(6);

        return root;
    }

    public static BiTreeNode generalSubBiTreeNode() {

        /**
         *              0
         *           1     2
         *        3     4
         *
         */
        BiTreeNode root = new BiTreeNode(0);

        root.left = new BiTreeNode(1);
        root.right = new BiTreeNode(2);

        root.left.left = new BiTreeNode(3);
        root.left.right = new BiTreeNode(4);

        return root;
    }

    public static List<Integer> biTreePreOrder(BiTreeNode root) {

        ArrayList<Integer> rets = new ArrayList<>();
        Stack<BiTreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            BiTreeNode value = stack.pop();
            if (value != null) {
                rets.add(value.value);
                stack.push(value.right);
                stack.push(value.left);
            }else {
                rets.add(null);
            }
        }

        return rets;
    }

    public static void pres(BiTreeNode head, ArrayList<String> ans) {
        if (head == null) {
            ans.add(null);
        } else {
            ans.add(String.valueOf(head.value + ""));
            pres(head.left, ans);
            pres(head.right, ans);
        }
    }

    public static void main(String[] args) {

        BiTreeNode root = generalBiTreeNode();
        BiTreeNode subRoot = generalSubBiTreeNode();
        List<Integer> list = biTreePreOrder(root);
        ArrayList<String> strings = new ArrayList<>();
        pres(root,strings);
        System.out.println(strings);
        ArrayList<String> strings1 = new ArrayList<>();
        pres(subRoot,strings1);
        System.out.println(strings1);
        List<Integer> list1 = biTreePreOrder(subRoot);
        System.out.println(list);
        System.out.println(list1);
    }
}
